import javafx.scene.Node;
import javafx.scene.effect.SepiaTone;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: MENG
 * Date: 2022-08-05
 * Time: 22:36
 */
public class OjTest {
    //只出现一次的数字
/*    //异或实现
    public int singleNum(int[] nums){
        int ret = 0;//
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return  ret;
    }*/


    //set实现
    public int singleNum(int[] nums){
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if(!set.contains(key)){
                set.add(key);
            }else{
                set.remove(key);
            }
        }
         //走到这里  集合当中  只剩下一个元素了  问题：如何找到这个元素
        for (int i = 0; i < nums.length; i++){
            if(set.contains(nums[i])){
                return nums[i];
            }
        }
        return -1;

    }

/*    //map实现
    public int singleNum(int[] nums){
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if(map.get(key) == null){
                map.put(key,1);
            }else {
                int val = map.get(key);
                map.put(key,val+1);
            }
        }
        Set<Map.Entry<Integer,Integer>> entrySet = map.entrySet();
        for (Map.Entry<Integer,Integer> entry: entrySet) {
            if(entry.getValue() == 1){
                return entry.getKey();
            }
        }
        return -1;
    }*/

/*        //复制带随机指针的链表
    public Node copyRandomList(Node head) {
        //这里不能用TreeMap
        Map<Node, Node> map = new HashMap<>();
        //1、第一次遍历链表
        Node cur = head;
        while(cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        //2、第二次遍历链表
        cur = head;//cur重新指向头结点
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);//返回新节点的头结点
    }*/

    //宝石与石头
    public int numJewelsInStones(String jewels, String stones){
        Set<Character> set = new HashSet<>();
        for (char ch : jewels.toCharArray()) {
            set.add(ch);
        }
        int count = 0;
        for (char ch : stones.toCharArray()) {
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    //前k个高频词
    public static List<String> topKFrequent(String[] words, int k){
        //1. 统计单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String key : words) {
            if(map.get(key) == null){
                map.put(key,1);
            }else{
                int val = map.get(key);
                map.put(key,val + 1);
            }
        }
        //2.建立大小为k的    小根堆
        PriorityQueue<Map.Entry<String,Integer>> minQ =
                new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        if(o1.getValue().compareTo(o2.getValue()) == 0){
                            //频率相同的时候  把这个变成以key 为准的大根堆
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());//根据频率建立小根堆
                    }
                });
        //3. 遍历map，先放满K个，然后从第K+1个开始 和堆顶元素比较
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minQ.size() < k){
                minQ.offer(entry);
            }else{
                //3.2 如果已经放满了小根堆，那么 我们需要让当前元素 和堆顶元素比较
                Map.Entry<String,Integer> top = minQ.peek();
                if(top != null){
                    if(entry.getValue() > top.getValue()){
                        minQ.poll();
                        minQ.offer(entry);
                    }else{
                        //<  ||  ==  3.3 此时考虑频率相同，key小的入队,<的不用管
                        if(top.getValue().compareTo(entry.getValue()) == 0){
                            if(top.getKey().compareTo(entry.getKey()) > 0){
                                minQ.poll();
                                minQ.offer(entry);
                            }
                        }
                    }
                }
            }
        }

        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minQ.poll();
            if(top != null){
                list.add(top.getKey());
            }
        }
        Collections.reverse(list);
        return list;


    }
    //字符串中第一个只出现一次字符
    public static int firstUniqChar(String s) {
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            count[ch - 97]++;
        }

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(count[ch-97] == 1){
                return i; //题目要求返回数组下标
            }
        }
        return -1;
    }

}
